SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Tree transducer</title>

</head>

Tree transducer

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">In <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a> and <a href="Formal_language_theory" class="mw-redirect" title="Formal language theory">formal language theory</a>, a tree transducer (TT) is an <a href="Abstract_machine" title="Abstract machine">abstract machine</a> taking as input a <a href="Tree_(automata_theory)" title="Tree (automata theory)">tree</a>, and generating output – generally other trees, but models producing <a href="Formal_language#Words_over_an_alphabet" title="Formal language">words</a> or other structures exist. Roughly speaking, tree transducers extend <a href="Tree_automata" class="mw-redirect" title="Tree automata">tree automata</a> in the same way that <a href="Finite-state_transducer" title="Finite-state transducer">word transducers</a> extend <a href="Finite-state_automata" class="mw-redirect" title="Finite-state automata">word automata</a>.

Manipulating tree structures instead of words enable TT to model syntax-directed transformations of formal or natural languages. However, TT are not as well-behaved as their word counterparts in terms of <a href="Computational_complexity_theory" title="Computational complexity theory">algorithmic complexity</a>, <a href="Closure_(mathematics)" title="Closure (mathematics)">closure properties</a>, etcetera. In particular, most of the main classes are not closed under <a href="Function_composition" title="Function composition">composition</a>.

The main classes of tree transducers are:

<div class="mw-heading mw-heading2"><h2 id="Top-Down_Tree_Transducers_(TOP)">Top-Down Tree Transducers (TOP)</h2></div>

A TOP T is a tuple (Q, Σ, Γ, I, δ) such that:

<ul><li>Q is a <a href="Finite_set" title="Finite set">finite set</a>, the set of states;</li>

<li>Σ is a finite <a href="Ranked_alphabet" title="Ranked alphabet">ranked alphabet</a>, called the input alphabet;</li>

<li>Γ is a finite ranked alphabet, called the output alphabet;</li>

<li>I is a <a href="Subset" title="Subset">subset</a> of Q, the set of initial states; and</li>

<li>δ is a set of rules of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}</annotation>

</semantics>

</math><img src="./d47c7ac29cb7e48d5a8779bff44b041547a01515.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.021ex; height:2.843ex;" alt="{\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}" loading="lazy">, where f is a symbol of Σ, n is the arity of f, q is a state, and u is a tree on Γ and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q\times 1..n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q\times 1..n}</annotation>

</semantics>

</math><img src="./db4eacdd8ef2de41097177f2e2b0a8775f285ecb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.53ex; height:2.509ex;" alt="{\displaystyle Q\times 1..n}" loading="lazy">, such pairs being <a href="Nullary" class="mw-redirect" title="Nullary">nullary</a>.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Examples_of_rules_and_intuitions_on_semantics">Examples of rules and intuitions on semantics</h3></div>

For instance,

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</msup>

<msub>

</mrow>

</msub>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(f(x_{1},\dots ,x_{3}))\to g(a,q'(x_{1}),h(q''(x_{3})))}</annotation>

</semantics>

</math><img src="./ae75d408d30e56fc6cf5cdb4c29d90d44e9f8338.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.265ex; height:3.009ex;" alt="{\displaystyle q(f(x_{1},\dots ,x_{3}))\to g(a,q'(x_{1}),h(q''(x_{3})))}" loading="lazy"></dd></dl>

is a rule – one customarily writes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(x_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(x_{i})}</annotation>

</semantics>

</math><img src="./f69464bec847bfb474f6a70ff1f7d05e3481f089.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.008ex; height:2.843ex;" alt="{\displaystyle q(x_{i})}" loading="lazy"> instead of the pair <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (q,x_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (q,x_{i})}</annotation>

</semantics>

</math><img src="./ec81c94b6a7a1c59b7f2194b4e9bb601d130da6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.042ex; height:2.843ex;" alt="{\displaystyle (q,x_{i})}" loading="lazy"> – and its intuitive semantics is that, under the action of q, a tree with f at the root and three children is transformed into

<msup>

</msup>

<msub>

</mrow>

</msub>

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(a,q'(x_{1}),h(q''(x_{3})))}</annotation>

</semantics>

</math><img src="./3516ec1a2d4ce8ac96b53825e1f06179146b61e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.738ex; height:3.009ex;" alt="{\displaystyle g(a,q'(x_{1}),h(q''(x_{3})))}" loading="lazy"></dd></dl>

where, recursively, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q'(x_{1})}">

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q'(x_{1})}</annotation>

</semantics>

</math><img src="./a15dc3ab82c26efd1a74d1640a7359dc2cd60268.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.957ex; height:3.009ex;" alt="{\displaystyle q'(x_{1})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q''(x_{3})}">

<msup>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q''(x_{3})}</annotation>

</semantics>

</math><img src="./0ad8a58d882d32b3b87a6a7d5afff0652942026e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.41ex; height:3.009ex;" alt="{\displaystyle q''(x_{3})}" loading="lazy"> are replaced, respectively, with the application of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q'}</annotation>

</semantics>

</math><img src="./912405e5d416048908ea7978929975843d2ee4e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.764ex; height:2.843ex;" alt="{\displaystyle q'}" loading="lazy"> on the first child and

with the application of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q''}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q''}</annotation>

</semantics>

</math><img src="./46bd61322618f638d67f20a848f1c63bb8b99e3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.217ex; height:2.843ex;" alt="{\displaystyle q''}" loading="lazy"> on the third.

<div class="mw-heading mw-heading3"><h3 id="Semantics_as_term_rewriting">Semantics as <a href="Term_rewriting_system" class="mw-redirect" title="Term rewriting system">term rewriting</a></h3></div>

The <a href="Semantics_(computer_science)" title="Semantics (computer science)">semantics</a> of each state of the transducer T, and of T itself, is a <a href="Binary_relation" title="Binary relation">binary relation</a> between input trees (on Σ) and output trees (on Γ).

A way of defining the semantics formally is to see <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"> as a <a href="Term_rewriting_system" class="mw-redirect" title="Term rewriting system">term rewriting system</a>, provided that in the right-hand sides the calls are written in the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(x_{i})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(x_{i})}</annotation>

</semantics>

</math><img src="./f69464bec847bfb474f6a70ff1f7d05e3481f089.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.008ex; height:2.843ex;" alt="{\displaystyle q(x_{i})}" loading="lazy">, where states q are unary symbols. Then the semantics <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [\![q]\!]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![q]\!]}</annotation>

</semantics>

</math><img src="./8d92050c3f031dc85a30f89cbc7a5f8bf08cb2e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.883ex; height:2.843ex;" alt="{\displaystyle [\![q]\!]}" loading="lazy"> of a state q is given by

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![q]\!]=\{u\mapsto v\mid u{\text{ is a tree on }}\Sigma ,\ v{\text{ is a tree on }}\Gamma {\text{, and }}q(u)\to _{\delta }^{*}v\}.}</annotation>

</semantics>

</math><img src="./3c52ceac34aae8ea7a1dbc346a595ad0e8db1111.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:63.654ex; height:3.009ex;" alt="{\displaystyle [\![q]\!]=\{u\mapsto v\mid u{\text{ is a tree on }}\Sigma ,\ v{\text{ is a tree on }}\Gamma {\text{, and }}q(u)\to _{\delta }^{*}v\}.}" loading="lazy"></dd></dl>

The semantics of T is then defined as the union of the semantics of its initial states:

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [\![T]\!]=\bigcup _{q\in I}[\![q]\!].}</annotation>

</semantics>

</math><img src="./0c36e3eece18514ce988f92b8ff673bef2b7a756.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:12.759ex; height:5.843ex;" alt="{\displaystyle [\![T]\!]=\bigcup _{q\in I}[\![q]\!].}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Determinism_and_domain">Determinism and domain</h3></div>

As with tree automata, a TOP is said to be deterministic (abbreviated DTOP) if no two rules of δ share the same left-hand side, and there is at most one initial state. In that case, the semantics of the DTOP is a <a href="Partial_function" title="Partial function">partial function</a> from input trees (on Σ) to output trees (on Γ), as are the semantics of each of the DTOP's states.

The domain of a transducer is the <a href="Domain_of_a_function" title="Domain of a function">domain</a> of its semantics. Likewise, the image of a transducer is the <a href="Image_(mathematics)" title="Image (mathematics)">image</a> of its semantics.

<div class="mw-heading mw-heading3"><h3 id="Properties_of_DTOP">Properties of DTOP</h3></div>

<ul><li>DTOP are not closed under <a href="Union_(mathematics)" class="mw-redirect" title="Union (mathematics)">union</a>: this is already the case for deterministic word transducers.</li>

<li>The domain of a DTOP is a <a href="Regular_tree_language" class="mw-redirect" title="Regular tree language">regular tree language</a>. Furthermore, the domain is recognisable by a deterministic top-down <a href="Tree_automaton" title="Tree automaton">tree automaton</a> (DTTA) of size at most exponential in that of the initial DTOP.<a href="#cite_note-1">[1]</a></li></ul>

<dl><dd><dl><dd>That the domain is DTTA-recognizable is not surprising, considering that the left-hand sides of DTOP rules are the same as for DTTA. As for the reason for the exponential explosion in the worst case (that does not exist in the word case), consider the rule <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))}</annotation>

</semantics>

</math><img src="./ab9d4fc9d36dc310c71e6bc0d4256d6d9a625062.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:39.626ex; height:2.843ex;" alt="{\displaystyle q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))}" loading="lazy">. In order for the computation to succeed, it must succeed for both children. That means that the right child must be in the domain of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{3}}</annotation>

</semantics>

</math><img src="./2a79626b787857474daa665c953bbc6725e7c345.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{3}}" loading="lazy">. As for the left child, it must be in the domain of both <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{2}}</annotation>

</semantics>

</math><img src="./43f1b08d7d69712872e051c2b33fdfa9f5d42319.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{2}}" loading="lazy">. Generally, since subtrees can be copied, a single subtree can be evaluated by multiple states during a run, despite the determinism, and unlike DTTA. Thus the construction of the DTTA recognising the domain of a DTOP must account for sets of states and compute the intersections of their domains, hence the exponential. In the special case of linear DTOP, that is to say DTOP where each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> appears at most once in the right-hand side of each rule, the construction is linear in time and space.</dd></dl></dd></dl>

<ul><li>The image of a DTOP is not a regular tree language.</li></ul>

<dl><dd><dl><dd>Consider the transducer coding the transformation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)\to g(x,x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)\to g(x,x)}</annotation>

</semantics>

</math><img src="./f2b6f286d9af1a671353b753125eae48712b350e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.65ex; height:2.843ex;" alt="{\displaystyle f(x)\to g(x,x)}" loading="lazy">; that is, duplicate the child of the input. This is easily done by a rule <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(f(x_{1}))\to g(p(x_{1}),p(x_{1}))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(f(x_{1}))\to g(p(x_{1}),p(x_{1}))}</annotation>

</semantics>

</math><img src="./ad37af92da9e58be6effe7b65623d7c386df1605.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.649ex; height:2.843ex;" alt="{\displaystyle q(f(x_{1}))\to g(p(x_{1}),p(x_{1}))}" loading="lazy">, where p encodes the <a href="Identity_(mathematics)" title="Identity (mathematics)">identity</a>. Then, absent any restrictions on the first child of the input, the image is a classical non-regular tree language.</dd></dl></dd></dl>

<ul><li>However, the domain of a DTOP cannot be restricted to a regular tree language. That is to say, given a DTOP T and a language L, one cannot in general build a DTOP <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T'}</annotation>

</semantics>

</math><img src="./4b32d735f4fbb6eff3b35ed3dc1005a069d0b2e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.405ex; height:2.509ex;" alt="{\displaystyle T'}" loading="lazy"> such that the semantics of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T'}">

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T'}</annotation>

</semantics>

</math><img src="./4b32d735f4fbb6eff3b35ed3dc1005a069d0b2e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.405ex; height:2.509ex;" alt="{\displaystyle T'}" loading="lazy"> is that of T, <a href="Restriction_(mathematics)" title="Restriction (mathematics)">restricted</a> to L.</li></ul>

<dl><dd><dl><dd>This property is linked to the reason deterministic top-down tree automata are less expressive than bottom-up automata: once you go down a given path, information from other paths is inaccessible. Consider the transducer coding the transformation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)\to y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)\to y}</annotation>

</semantics>

</math><img src="./46a654e34f0b880da7571c09e19c8f0de03cb1ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.377ex; height:2.843ex;" alt="{\displaystyle f(x,y)\to y}" loading="lazy">; that is, output the right child of the input. This is easily done by a rule <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(f(x_{1},x_{2}))\to p(x_{2})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(f(x_{1},x_{2}))\to p(x_{2})}</annotation>

</semantics>

</math><img src="./f76f2523748640c15ce37e0638af9d78e7e3e426.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.745ex; height:2.843ex;" alt="{\displaystyle q(f(x_{1},x_{2}))\to p(x_{2})}" loading="lazy">, where p encodes the identity. Now let's say we want to restrict this transducer to the finite (and thus, in particular, regular) domain <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{f(c,a),\ f(c,b)\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{f(c,a),\ f(c,b)\}}</annotation>

</semantics>

</math><img src="./fefdc87bd1d5542e1f3382ee51bd9f3bcf38c8ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.424ex; height:2.843ex;" alt="{\displaystyle \{f(c,a),\ f(c,b)\}}" loading="lazy">. We must use the rules <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q(f(x_{1},x_{2}))\to p(x_{2}),\ p(a)\to a,\ p(b)\to b}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q(f(x_{1},x_{2}))\to p(x_{2}),\ p(a)\to a,\ p(b)\to b}</annotation>

</semantics>

</math><img src="./8f9c449506ebef563c696ebd9eb1682e7166e329.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.615ex; height:2.843ex;" alt="{\displaystyle q(f(x_{1},x_{2}))\to p(x_{2}),\ p(a)\to a,\ p(b)\to b}" loading="lazy">. But in the first rule, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation>

</semantics>

</math><img src="./a8788bf85d532fa88d1fb25eff6ae382a601c308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}" loading="lazy"> does not appear at all, since nothing is produced from the left child. Thus, it is not possible to test that the left child is c. In contrast, since we produce from the right child, we can test that it is a or b. In general, the criterion is that DTOP cannot test properties of subtrees from which they do not produce output.</dd></dl></dd></dl>

<ul><li>DTOP are not closed under <a href="Function_composition" title="Function composition">composition</a>. However this problem can be solved by the addition of a lookahead: a tree automaton, coupled to the transducer, that can perform tests on the <a href="Domain_of_a_function" title="Domain of a function">domain</a> which the transducer is incapable of.<a href="#cite_note-2">[2]</a></li></ul>

<dl><dd><dl><dd>This follows from the point about domain restriction: composing the DTOP encoding identity on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{f(c,a),\ f(c,b)\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{f(c,a),\ f(c,b)\}}</annotation>

</semantics>

</math><img src="./fefdc87bd1d5542e1f3382ee51bd9f3bcf38c8ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.424ex; height:2.843ex;" alt="{\displaystyle \{f(c,a),\ f(c,b)\}}" loading="lazy"> with the one encoding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x,y)\to y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x,y)\to y}</annotation>

</semantics>

</math><img src="./46a654e34f0b880da7571c09e19c8f0de03cb1ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.377ex; height:2.843ex;" alt="{\displaystyle f(x,y)\to y}" loading="lazy"> must yield a transducer with the semantics <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{f(c,a)\mapsto a,\ f(c,b)\mapsto b\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{f(c,a)\mapsto a,\ f(c,b)\mapsto b\}}</annotation>

</semantics>

</math><img src="./41ea4895f777d2e5cfaf31a84bc07926acae376e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:25.88ex; height:2.843ex;" alt="{\displaystyle \{f(c,a)\mapsto a,\ f(c,b)\mapsto b\}}" loading="lazy">, which we know is not expressible by a DTOP.</dd></dl></dd></dl>

<ul><li>The <a href="Typechecking" class="mw-redirect" title="Typechecking">typechecking</a> problem—testing whether the image of a regular tree language is included in another regular tree language—is decidable.</li>

<li>The <a href="Equivalence_problem" title="Equivalence problem">equivalence problem</a>—testing whether two DTOP define the same functions—is decidable.<a href="#cite_note-3">[3]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Bottom-Up_Tree_Transducers_(BOT)">Bottom-Up Tree Transducers (BOT)</h2></div>

As in the simpler case of tree automata, bottom-up tree transducers are defined similarly to their top-down counterparts, but proceed from the leaves of the tree to the root, instead of from the root to the leaves. Thus the main difference is in the form of the rules, which are of the form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(q_{1}(x_{1}),\dots ,q_{n}(x_{n}))\to q(u)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(q_{1}(x_{1}),\dots ,q_{n}(x_{n}))\to q(u)}</annotation>

</semantics>

</math><img src="./7b3292c39681b696d5690545d9572d24617013b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.986ex; height:2.843ex;" alt="{\displaystyle f(q_{1}(x_{1}),\dots ,q_{n}(x_{n}))\to q(u)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFComon_et_al.2008" class="citation book cs1">Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (November 2008). <a rel="nofollow" class="external text" href="https://hal.inria.fr/hal-03367725/document">"Chapter 6: Tree Transducers"</a>. Tree Automata Techniques and Applications. Retrieved 11 February 2014.</cite></li>

<li><cite id="CITEREFHosoya2010" class="citation book cs1">Hosoya, Haruo (4 November 2010). Foundations of XML Processing: The Tree-Automata Approach. Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-139-49236-2</bdi>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> Baker, B.S.: Composition of top-down and bottom-up tree transductions. Inf. Control 41(2), 186–213 (1979)

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFManeth2015" class="citation journal cs1">Maneth, Sebastian (December 2015). <a rel="nofollow" class="external text" href="https://www.pure.ed.ac.uk/ws/files/25073983/survey_1.pdf">"A Survey on Decidable Equivalence Problems for Tree Transducers"</a> (PDF). International Journal of Foundations of Computer Science. 26 (8): 1069–1100. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1142%2FS0129054115400134">10.1142/S0129054115400134</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/20.500.11820%2F2f1acef4-1b06-485f-bfd1-88636c9e2fe6">20.500.11820/2f1acef4-1b06-485f-bfd1-88636c9e2fe6</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite class="citation journal cs1"><a rel="nofollow" class="external text" href="http://www.inf.u-szeged.hu/actacybernetica/edb/vol05n1/Esik_1980_ActaCybernetica.xml">"Decidability results concerning tree transducers I"</a>. www.inf.u-szeged.hu.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-14" href="https://en.wikipedia.org/wiki/?title=Tree_transducer&oldid=1285525554">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>